Easy
LeetCode Link: https://leetcode.com/problems/two-sum/description/
Other References:
https://www.youtube.com/watch?v=UXDSeD9mN-k
https://takeuforward.org/data-structure/two-sum-check-if-a-pair-with-given-sum-exists-in-array/
Variant 1
Problem
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
1. package com.leetcode.solutions._1_to_100._1TwoSum.v1;
2.
3. public class _1BruteForceSolution {
4. public int[] twoSum(int[] nums, int target) {
5. int[] ans = new int[2];
6. ans[0] = ans[1] = -1;
7. for (int i = 0; i < nums.length; i++) {
8. for (int j = i + 1; j < nums.length; j++) {
9. if (nums[i] + nums[j] == target) {
10. ans[0] = i;
11. ans[1] = j;
12. return ans;
13. }
14. }
15. }
16. return ans;
17. }
18.
19. public static void main(String args[]) {
20. _1BruteForceSolution solObj = new _1BruteForceSolution();
21. int[] nums = {3,2,4};
22. int target = 6;
23. int[] ans = solObj.twoSum(nums, target);
24. System.out.println("This is the answer: [" + ans[0] + ", "
25. + ans[1] + "]");
26. }
27. }
28.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
Constraints:
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.
Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?
Sol 1 - Naive Approach (Brute-force approach)
Intuition:
For each element of the given array, we will try to search for another element such that its sum is equal to the target. If such two numbers exist, we will return the indices accordingly.
Approach:
First, we will use a loop(say i) to select the indices of the array one by one.
For every index i, we will traverse through the remaining array using another loop(say j) to find the other number such that the sum is equal to the target (i.e. arr[i] + arr[j] = target).
In every iteration, if the inner loop starts from index 0, we will be checking the same pair of numbers multiple times. For example, in iteration 1, for i = 0, we will check for the pair arr[0] and arr[1]. Again in iteration 2, for i = 1, we will check arr[1] and arr[0]. So, to eliminate these same pairs, we will start the inner loop from i+1.
Time & Space Complexity | O(N2) | O(1)
Time Complexity: O(N2), where N = size of the array. Reason: There are two loops(i.e. nested) each running for approximately N times.
Space Complexity: O(1) as we are not using any extra space.
Time Complexity:
The method has two nested loops:
Outer loop (with index i): Runs from 0 to n-1, where n is the length of the array nums.
Inner loop (with index j): Runs from i+1 to n-1.
In the worst case, the outer loop runs n times, and for each iteration of i, the inner loop runs n-i-1 times. So, the total number of iterations is:
Thus, the time complexity is O(n2).
Space Complexity:
The algorithm uses only a constant amount of extra space, i.e., an array ans of size 2, which does not grow with the size of the input array nums.
No additional data structures that depend on n are used.
Thus, the space complexity is O(1).
Sol 2 - Better Approach (using Hashing)
We will store the element along will its index in the HashMap. Thus we can easily retrieve the index of the other element i.e. target-(selected element) without iterating the array.
Note:
Pro – we can even remove the variable at line 9, currentNumber. But, I have kept it for clarity purpose.
Pro – also, if we have duplicate elements, then we should define the map as <Integer, List<Integer>>. Though duplicate is not mentioned in the problem.
Time & Space Complexity | O(n) | O(n)
Time Complexity: O(n)
Linear time due to the single traversal of the nums array and O(1) operations for the HashMap.
Space Complexity: O(n)
Space is required to store at most n elements in the HashMap.
Variant 2
Problem
Given an array of integers arr[] and an integer target.
Output: Return YES if there exist two numbers such that their sum is equal to the target. Otherwise, return NO.
Example 1:
Input Format: N = 5, arr[] = {2,6,5,8,11}, target = 14
Result: YES
Explanation: arr[1] + arr[3] = 14. So, the answer is “YES” for the first variant.
Example 2:
Input Format: N = 5, arr[] = {2,6,5,8,11}, target = 15
Result: NO
Explanation: There exist no such two numbers whose sum is equal to the target.
Sol 1 - Naive Approach (Brute-force approach)
Intuition:
For each element of the given array, we will try to search for another element such that its sum is equal to the target. If such two numbers exist, we will return YES or NO accordingly.
Approach:
First, we will use a loop(say i) to select the indices of the array one by one.
For every index i, we will traverse through the remaining array using another loop(say j) to find the other number such that the sum is equal to the target (i.e. arr[i] + arr[j] = target).
In every iteration, if the inner loop starts from index 0, we will be checking the same pair of numbers multiple times. For example, in iteration 1, for i = 0, we will check for the pair arr[0] and arr[1]. Again in iteration 2, for i = 1, we will check arr[1] and arr[0]. So, to eliminate these same pairs, we will start the inner loop from i+1.
Time & Space Complexity | O(N2) | O(1)
Time Complexity: O(N2), where N = size of the array. Reason: There are two loops(i.e. nested) each running for approximately N times.
Space Complexity: O(1) as we are not using any extra space.
Time Complexity:
The method has two nested loops:
Outer loop (with index i): Runs from 0 to n-1, where n is the length of the array nums.
Inner loop (with index j): Runs from i+1 to n-1.
In the worst case, the outer loop runs n times, and for each iteration of i, the inner loop runs n-i-1 times. So, the total number of iterations is:
Thus, the time complexity is O(n2).
Space Complexity:
The algorithm uses only a constant amount of extra space, i.e., an array ans of size 2, which does not grow with the size of the input array nums.
No additional data structures that depend on n are used.
Thus, the space complexity is O(1).
Sol 2 - Better Approach (using Hashing)
Intuition:
Basically, in the previous approach we selected one element and then searched for the other one using a loop. Here instead of using a loop, we will use the HashMap to check if the other element i.e. target-(selected element) exists. Thus, we can trim down the time complexity of the problem.
And for the second variant, we will store the element along will its index in the HashMap. Thus we can easily retrieve the index of the other element i.e. target-(selected element) without iterating the array.
Approach:
The steps are as follows:
We will select the element of the array one by one using a loop (say i).
Then we will check if the other required element (i.e. target-arr[i]) exists in the hashMap.
If that element exists, then we will return “YES” for the first variant or we will return the current index i.e. i, and the index of the element found using map i.e. mp[target-arr[i]].
If that element does not exist, then we will just store the current element in the hashMap along with its index. Because in the future, the current element might be a part of our answer.
Finally, if we are out of the loop, that means there is no such pair whose sum is equal to the target. In this case, we will return either “NO” or {-1, -1} as per the variant of the question.
Dry Run: Given array, nums = [2,3,1,4], target = 4
Note:
Pro – we can even remove the variable at line 9, currentNumber. But, I have kept it for clarity purpose.
Pro – also, if we have duplicate elements, then we should define the map as <Integer, List<Integer>>. Though duplicate is not mentioned in the problem.
Time & Space Complexity | O(n) | O(n)
Time Complexity: O(n)
Linear time due to the single traversal of the nums array and O(1) operations for the HashMap.
Space Complexity: O(n)
Space is required to store at most n elements in the HashMap.
Sol 3 - Better Approach (using two-pointer)
This approach is only slightly better than the solution 2 using HashMap.
This is only applicable if the interviewer tells us not to use Map.
Note:
This will also not be possible for Variant 1 above, as here we will sort the array and the indices will be lost and in Variant 1 we were returning the indices.
Intuition: In this approach, we will first sort the array and will try to choose the numbers in a greedy way.
We will keep a left pointer at the first index and a right pointer at the last index. Now until left < right, we will check the sum of arr[left] and arr[right]. Now if the sum < target, we need bigger numbers and so we will increment the left pointer. But if sum > target, we need to consider lesser numbers and so we will decrement the right pointer.
If sum == target we will return either “YES” or the indices as per the question. But if the left crosses the right pointer, we will return “NO” or {-1, -1}.
Approach:
The steps are the following:
We will sort the given array first.
Now, we will take two pointers i.e. left, which points to the first index, and right, which points to the last index.
Now using a loop we will check the sum of arr[left] and arr[right] until left < right.
If arr[left] + arr[right] > sum, we will decrement the right pointer.
If arr[left] + arr[right] < sum, we will increment the left pointer.
If arr[left] + arr[right] == sum, we will return the result.
Finally, if no results are found we will return “No” or {-1, -1}.
Time & Space Complexity | O(n log n) | O(n)
Time Complexity: O(n log n)
This is dominated by the sorting step. The two-pointer traversal itself is linear, i.e., O(n), but the sorting takes O(n log n).
Space Complexity: O(n)
The space used by the sorting algorithm dominates the space complexity, as it requires O(n) space in the worst case.
But if we do not consider any new extra space for sorting the same array, then it will be O(1).
Note: ChatGPT
O(n) is better than O(n log n), particularly as n grows large.
Small Inputs:
For smaller values of n, the difference in performance might be negligible. Algorithms with O(n log n) might perform just as well as those with O(n), especially when optimizations (like parallelization) are considered.
Large Inputs:
As the input size grows, the difference between O(n) and O(n log n) becomes more significant. For very large datasets (millions of elements), the O(n log n) complexity will result in a noticeable performance hit.
Medium
Link: https://leetcode.com/problems/add-two-numbers/description/
References:
https://www.youtube.com/watch?v=XmRrGzR6udg
https://takeuforward.org/data-structure/add-two-numbers-represented-as-linked-lists/
Problem
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example 1:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
Example 2:
Input: l1 = [0], l2 = [0]
Output: [0]
Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
Constraints:
The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.
Solution 1
Intuition
Normal Case Examples:
Step by Step Solution:
As we know that the numbers are already in reversed order so we can directly start adding the 2 points from the start of the two nodes.
Also we will keep 2 more variables SUM to store the sum value and the CARRY to store the carry value.
First 4 + 1 = 5
So SUM = 5 and CARRY = 0
Step 2:
9 + 9
Step 3:
9 + 7 + 1 (CARRY)
Step 4:
5 + 1 (CARRY)
Step 5:
9 + 0 (CARRY)
Done!
Solution 1
Initially:
carry = sum / 10; // Integer division, floor of sum divided by 10
sum = sum % 10; // Remainder when sum is divided by 10
After 1st pass:
9 + 9 = 18
This is done so that if we have a carry, then it will create a new node with it’s value.
Pro – here why we are only checking carry as 1, why not any other number?
in the context of adding two digits (0-9) and considering their sum, the carry will always be either 0 or 1.
What Are the Possible Values for Carry?
The sum of two digits from 0-9 can be at most:
9+9+1=19
(where the extra 1 comes from a previous carry)
The carry calculation:
carry=sum/10
If sum < 10, then carry = 0
If sum ≥ 10, then carry = 1
Since the maximum possible sum is 19, integer division 19 / 10 gives 1.
Conclusion
The possible values for carry are only 0 or 1—it can never be 2 or more because the maximum sum of two digits plus carry is 19.
Pro in short, max 2 digits while addition can be 9 + 9 = 18, so max carry will always be 1 or zero.
At the end we return result.next because the first one was 0 as shown in the right side above. And our answer would be rest of the number except 0.
Time Complexity: O(max(m,n)). Assume that m and n represent the length of l1 and l2 respectively, the algorithm above iterates at most max(m,n) times.
Space Complexity: O(max(m,n)). The length of the new list is at most max(m,n)+1.
Thanks for Reading!